//
//  BinarySearchTree.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/15.
//

import Foundation

/// 二叉搜索树（无重复数据）
class BinarySearchTree {
    private(set) var tree: BinaryTreeNode<Int>? = nil
    
    func find(_ data: Int) -> BinaryTreeNode<Int>? {
        var p = tree
        while p != nil {
            if data < p!.data {
                p = p?.leftNode
            } else if data > p!.data {
                p = p?.rightNode
            } else {
                return p
            }
        }
        return nil
    }
    
    func inset(_ data: Int) {
        if tree == nil {
            tree = BinaryTreeNode(data)
            return
        }
        
        var p = tree
        while p != nil {
            if data > p!.data {
                if p?.rightNode == nil {
                    p?.rightNode = BinaryTreeNode(data)
                    return
                }
                p = p?.rightNode
            } else {
                if p?.leftNode == nil {
                    p?.leftNode = BinaryTreeNode(data)
                    return
                }
                p = p?.leftNode
            }
        }
    }
    
    func delete(_ data: Int) {
        // p指向要删除的节点
        var p = tree
        // pp记录的是p的父节点
        var pp: BinaryTreeNode<Int>? = nil
        while p != nil && p!.data != data {
            pp = p
            if data > p!.data {
                p = p?.rightNode
            } else {
                p = p?.leftNode
            }
        }
        if p == nil {
            // 没有找到
            return
        }
        
        // 要删除的节点有两个子节点
        if p?.leftNode != nil && p?.rightNode != nil { //找右子树的最小节点
            var minP = p!.rightNode
            var minPP = p
            while minP?.leftNode != nil {
                minPP = minP
                minP = minP?.leftNode
            }
            p?.data = minP!.data // 将minP的数据替换到p中
            p = minP // 下面就变成删除minP了
            pp = minPP
        }
        
        // 删除节点是叶子节点或者只有一个子节点
        var child: BinaryTreeNode<Int>? = nil
        if p?.leftNode != nil {
            child = p?.leftNode
        } else if p?.rightNode != nil {
            child = p?.rightNode
        } else {
            child = nil
        }
        
        if pp == nil {
            // 删除的是根节点
            tree = child
        } else if pp!.leftNode === p {
            pp?.leftNode = child
        } else {
            pp?.rightNode = child
        }
    }
}
